package leetcode_21_40;

import java.util.*;
import java.util.stream.Collectors;

public class findSubstring_30 {
    /**
     * 返回所有串联子串在 s 中的开始索引
     * 目前思路按照串联子串的长度进行循环截取 比较
     * 设置一个动态变化的集合，每匹配一个就删除一个字符串
     * 要求是串联字串之间可以互相重叠
     * 太慢了
     * @param s     字符串 s
     * @param words 长度相同的字符串集合
     * @return
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        int   str_len = words[0].length(),   //字符串长度
                words_size = words.length,  //字符串个数
                len=str_len * words_size;       //串联子串长度
        List<Integer>result=new ArrayList<>();
        if(len>s.length())
            return result;
        List<String> strs = new ArrayList<>(Arrays.asList(words));
        boolean flag=false;                                     //判断上一次是否完全匹配
        String last_len_str="";                                 //上一次完全匹配的串联子串
        for (int i = 0; i < s.length();) {
            List<String> now_strs =strs.stream().collect(Collectors.toList());                //用来操作的字符串集合重新赋值,集合深度拷贝,而不是引用浅拷贝
            if(i + len > s.length()) break;       //当剩余长度不够时，直接退出
            if( i !=0 && last_len_str.equals(s.substring(i,i+len)) ){
                if(flag==true){
                    result.add(i);
                }else
                    flag=false;
                i++;
                continue;
            }
            for (int t = i; t < i + len && i + len <= s.length() ; t += str_len) {      //一个小字符串
                String now_str = s.substring(t, t + str_len);
                if (now_strs.contains(now_str)) {         //如果匹配到了字符串，继续进行匹配
                     now_strs.remove(now_str);
                }else                       //如果匹配不到，直接退出
                    break;
            }
            if(now_strs.size()==0){        //完全匹配则添加起始索引到结果中
                result.add(i);
                flag=true;
                last_len_str=s.substring(i,i+len);  //更新
                if( i+1!=s.length()&&s.charAt(i)==s.charAt(i+1))     //特殊情况，下一个字符等于上一个
                    i++;
                else i+=str_len;           //直接跳过str_len个长度
                continue;
            }
            i++;
        }
        return result;
    }

    /**
     *滑动窗口算法
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        // 所有单词的个数
        int num = words.length;
        // 每个单词的长度（是相同的）
        int wordLen = words[0].length();
        // 字符串长度
        int stringLen = s.length();

        for (int i = 0; i < wordLen; i++) {                     //因为是滑动窗口处理，分组情况只有wordLen种
            //如aaabbbcccd
            //aa ab bb cc 向下滑动  / aa bb bc cc   向下滑动
            // 遍历的长度超过了整个字符串的长度，退出循环
            if (i + num * wordLen > stringLen) {
                break;
            }
            // differ表示窗口中的单词频次和words中的单词频次之差
            Map<String, Integer> differ = new HashMap<>();
            // 初始化窗口，窗口长度为num * wordLen,依次计算窗口里每个切分的单词的频次
            for (int j = 0; j < num; j++) {
                String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
            }
            // 遍历words中的word，对窗口里每个单词计算差值
            for (String word : words) {
                differ.put(word, differ.getOrDefault(word, 0) - 1);       //getOrDefault，有这个值就返回这个值,没有就用0代替
                // 差值为0时，移除掉这个word
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
            }
            // 开始滑动窗口
            for (int start = i; start < stringLen - num * wordLen + 1; start += wordLen) {
                if (start != i) {        //第一组无法滑动
                    // 右边的单词滑进来
                    String word = s.substring(start + (num - 1) * wordLen, start + num * wordLen);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);   //滑进来后，该word的原有差值加1
                    if (differ.get(word) == 0) {      //右边滑动进来后，窗口内该word的个数正好与字符串数组中相同
                        // 即差值为0，直接去掉differ中该word
                        differ.remove(word);
                    }
                    // 左边的单词滑出去
                    word = s.substring(start - wordLen, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1); //滑出去后，该word的原有差值减1，
                    // 如果是不相干的初始值是1，减1直接为0也就达到了滑出去的目的
                    if (differ.get(word) == 0) {
                        //左边滑出去后，差值为0
                        differ.remove(word);
                    }
                    word = s.substring(start - wordLen, start);
                }
                // 窗口匹配的单词数等于words中对应的单词数时，differ中全部消除
                if (differ.isEmpty()) {
                    res.add(start);
                }
            }
        }
        return res;
    }
}
